package com.ycl.javacore.algorithm;

/**
 * User: OF1089 杨成龙
 * Date: 2019/8/15
 * Time: 4:34 PM
 * Desc: 整数矩阵，最小路径和
 */
public class AlgoCast51 {
    public int miniPath(int[][] a) {
        int m = a.length;
        int n = a[0].length;
        int[][] p = new int[m][n];

        p[0][0] = a[0][0];

        for (int i = 1; i < m; i++) {
            p[i][0] = p[i - 1][0] + a[i][0];
        }

        for (int j = 1; j < n; j++) {
            p[0][j] = p[0][j - 1] + a[0][j];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                p[i][j] = Math.min(p[i - 1][j], p[i][j - 1]) + a[i][j];
            }
        }
        return p[m - 1][n - 1];
    }
}
